Recently, a method of encoding data using LDPC code has been highlighted. As most elements of a parity check matrix H are ‘0’, the LDPC code has been suggested as a linear block code of low density by Gallager in 1962. The LDPC code could not have been implemented by hardware technique at that time due to its complexity. Although the LDPC code has not attracted attention at that time, its excellent performance of the LDPC code has been approved in 1995. Thus, studies of the LDPC code have been actively made since 1995. (References: [1] Robert G. Gallager, “Low-Density Parity-Check Codes”, The MIT Press, Sep. 15, 1963, [2] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, IT-45, pp. 399-431(1999)) 2 0 Since a parity check matrix of the LDPC code has a very small number of elements of 1, decoding can be performed through repetitive decoding even in a very great block size, whereby its performance is approximate to channel capacity limitation of Shannon like turbo code if the block size becomes very great. In the parity check matrix, the number of 1 included in rows or columns will be referred to as weight.
The LDPC code can be explained by a parity check matrix H of (n−k)×n. A generator matrix G corresponding to the parity check matrix H can be obtained by the following equation 1.H·G=0  [Equation 1]
In the method of encoding and decoding data using LDPC code, a transmitter can encode input data using the generator matrix G in accordance with the following equation 2, wherein the generator matrix G has a relation of equation 1 with the parity check matrix H.c=G·x (wherein, c is a codeword and x is an information bit)  [Equation 2]
Hereinafter, a method of decoding data using the matrix H in accordance with the related art will be described.
A decoder of a receiver should obtain an information bit (x) from the codeword that is the encoding result of the transmitter. In this case, the decoder uses a feature of Hc=0. Namely, supposing that a received codeword is c′, the decoder calculates the value of Hc′. If the calculated result is 0, the decoder determines k number of bits in front of c′ as decoded information bits. If the value of Hc′ is not 0, the decoder obtains c′ which satisfies 0 using a sum-product algorithm through a graph, a belief algorithm, etc., thereby recovering x. The aforementioned check equation, Hc′=0 can be changed to c′HT=0 in accordance with the relation between the information bit and the matrix G.
FIG. 1 is a diagram illustrating a parity check matrix H through a bipartite graph. In FIG. 1, CNU represents a check node unit, and VNU represents a variable node unit. The decoding procedure using an algorithm on the bipartite graph includes the following three steps:
1. probability value update from a check node to a variable node;
2. probability value update from a variable node to a check node; and
3. decision of a decoding value through probability of a variable node.
First of all, the first step of performing update of the check node is performed through an initialization step, wherein a probability value received from a channel is input in the initialization step. After the first step is performed, if the probability value from the variable node to the check node is updated, the second step is performed. After the first and second steps are performed, the decoding value is decided using the probability value received from the channel and the probability value updated through the first and second steps.
The decoding procedure includes deciding the value c′ as the decoded value if the decided decoding value c′ satisfies a check equation Hc′=0, or includes iterating the first and second steps until the decoding value c′ satisfies the check equation if not so. The probability value update steps are performed in the first step and the second step in such a manner that each update step is iterated by the number of non-zero elements, i.e., ‘1’ belonging to each row or column of the parity check matrix. Namely, the check to variable update step of the first step are and the variable to check update step of the second step are performed in the position corresponding to the weight of the parity check matrix H. As the first and second steps are iterated, reliability of the probability value between the check node and the variable node is improved, and, as a result, the probability value is approximated to a true value of the codeword to be obtained.
For recent LDPC encoding, a method for encoding input data using the parity check matrix H without the generator matrix G is generally used. As described above, the parity check matrix H may be the most important factor in the encoding method using an LDPC code. Since the parity check matrix H has a size more than 1000×2000, approximately, problems occur in that the parity check matrix H requires many processing steps in the encoding and decoding steps, is accompanied with complexity in its application, and requires a lot of storage areas.